{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarray With Elements Greater Than Varying Threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #union-find #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #并查集 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: validSubarraySize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #元素值大于变化阈值的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>threshold</code>&nbsp;。</p>\n",
    "\n",
    "<p>找到长度为 <code>k</code>&nbsp;的&nbsp;<code>nums</code>&nbsp;子数组，满足数组中&nbsp;<strong>每个</strong>&nbsp;元素都 <strong>大于</strong>&nbsp;<code>threshold / k</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回满足要求的 <strong>任意</strong>&nbsp;子数组的 <strong>大小</strong>&nbsp;。如果没有这样的子数组，返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组中一段连续非空的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,4,3,1], threshold = 6\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>子数组 [3,4,3] 大小为 3 ，每个元素都大于 6 / 3 = 2 。\n",
    "注意这是唯一合法的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [6,5,6,5,8], threshold = 7\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>子数组 [8] 大小为 1 ，且 8 &gt; 7 / 1 = 7 。所以返回 1 。\n",
    "注意子数组 [6,5] 大小为 2 ，每个元素都大于 7 / 2 = 3.5 。\n",
    "类似的，子数组 [6,5,6] ，[6,5,6,5] ，[6,5,6,5,8] 都是符合条件的子数组。\n",
    "所以返回 2, 3, 4 和 5 都可以。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], threshold &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarray-with-elements-greater-than-varying-threshold](https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarray-with-elements-greater-than-varying-threshold](https://leetcode.cn/problems/subarray-with-elements-greater-than-varying-threshold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,3,1]\\n6', '[6,5,6,5,8]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = math.ceil(threshold/nums[i]) if threshold%nums[i]!=0 else math.ceil(threshold/nums[i])+1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>len(nums) or (i+1<len(nums) and nums[i+1]>=nums[i]):\n",
    "                continue\n",
    "            l = i-1\n",
    "            r = i+1\n",
    "            while(l>=0 and nums[l]<=nums[i] and r-l-1<nums[i]):\n",
    "                l -= 1\n",
    "            while(r<len(nums) and nums[r]<=nums[i] and r-l-1<nums[i]):\n",
    "                r += 1\n",
    "            if r-l-1 >= nums[i]:\n",
    "                return r-l-1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        stack = [[0, -1]]\n",
    "        inf = float('inf')\n",
    "        for i, n in enumerate(chain(nums, [0])):\n",
    "            _min, accu = inf, 0\n",
    "            while stack[-1][0] > n:\n",
    "                v, _ = stack.pop()\n",
    "                _min = min(_min, v)\n",
    "                if _min * (i - stack[-1][1] - 1) > threshold:\n",
    "                    return i - stack[-1][1] - 1\n",
    "            if n > stack[-1][0]:\n",
    "                stack.append([n, 0])\n",
    "            stack[-1][1] = i\n",
    "        return -1\n",
    "\n",
    "        # _max <= threshold\n",
    "        # _min*L <= threshold\n",
    "\n",
    "        # _max > threshold / k\n",
    "        # \n",
    "        # k = (thresold+_max) // _max .. L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums, threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 定义左边界\n",
    "        left_b = [-1 for _ in range(n)]\n",
    "        left = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while left and v <= nums[left[-1]]:\n",
    "                left.pop()\n",
    "            if left: left_b[i] = left[-1]\n",
    "            left.append(i)\n",
    "        # 定义右边界\n",
    "        right_b = [n for _ in range(n)]\n",
    "        right = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while right and nums[i] <= nums[right[-1]]:\n",
    "                right.pop()\n",
    "            if right: right_b[i] = right[-1]\n",
    "            right.append(i)\n",
    "        for i, v in enumerate(nums):\n",
    "            all_size = right_b[i] - left_b[i] - 1\n",
    "            if v > threshold // all_size:\n",
    "                return all_size\n",
    "        return -1\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        right = [n] * n\n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[i] <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[i] <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            l = st[-1] if st else -1\n",
    "            k = right[i] - l - 1\n",
    "            if nums[i] > threshold / k:\n",
    "                return k\n",
    "            st.append(i)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, st = [-1] * n, []  \n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] >= x:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        right, st = [n] * n, []  \n",
    "        for j in range(n - 1, - 1, -1):\n",
    "            while st and nums[st[-1]] >= nums[j]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[j] = st[-1]\n",
    "            st.append(j)\n",
    "        for num, l, r in zip(nums, left, right):\n",
    "            k = r - l - 1\n",
    "            if num > threshold // k:\n",
    "                return k\n",
    "        return -1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            leng = right[i] - left[i] - 1\n",
    "            if threshold / leng < nums[i]:\n",
    "                return leng\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            k = right[i] - left[i] - 1\n",
    "            if threshold / k < nums[i]:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        N = len(nums)\n",
    "        lt, st = [-1]*N, [] \n",
    "        for i,x in enumerate(nums): \n",
    "            while st and nums[st[-1]] >= x: \n",
    "                st.pop() \n",
    "            if st: lt[i] = st[-1] \n",
    "            st.append(i) \n",
    "        rt, st = [N]*N, [] \n",
    "        for i in range(N-1, -1, -1): \n",
    "            while st and nums[st[-1]] >= nums[i]: \n",
    "                st.pop() \n",
    "            if st:  rt[i] = st[-1] \n",
    "            st.append(i) \n",
    "        for i in range(N): \n",
    "            k = (rt[i] - lt[i] - 1)\n",
    "            if nums[i] > threshold / k: \n",
    "                return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # # 1. 并查集：子数组长度越大，thredhold/k就越小，满足要求\n",
    "        # ## 把考虑过的元素都串起来，这条链长度为k，动态维护每条连的长度，高效串联两条链\n",
    "        # n = len(nums)\n",
    "        # fa = list(range(n + 1))\n",
    "        # sz = [0] * (n + 1)\n",
    "        # def find(x:int)-> int:\n",
    "        #     if fa[x] != x:\n",
    "        #         fa[x] = find(fa[x])\n",
    "        #     return fa[x]\n",
    "        # for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "        #     j = find(i + 1)\n",
    "        #     fa[i] = j\n",
    "        #     sz[j] += sz[i] + 1\n",
    "        #     if num > threshold // sz[j] : return sz[j]\n",
    "        # return -1\n",
    "    \n",
    "        # 2. 单调栈：枚举左右边界\n",
    "        n = len(nums)\n",
    "        left, st = [-1] * n, []  # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）\n",
    "        for i, v in enumerate(nums):\n",
    "            while st and nums[st[-1]] >= v: st.pop()\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        right, st = [n] * n, []  # right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and nums[st[-1]] >= nums[i]: st.pop()\n",
    "            if st: right[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        for num, l, r in zip(nums, left, right):\n",
    "            k = r - l - 1\n",
    "            if num > threshold // k: return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 用单调栈求下一个大（或小）的元素，看到这种想单调栈\n",
    "        n = len(nums)\n",
    "        # left[i] 为左侧小于nums[i]的最近元素的位置，如果不存在的话，则为-1\n",
    "        left, stack = [-1] * n, []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] >= v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        # right[i] 为右侧小于nums[i]的最近元素的位置，如果不存在，则为n\n",
    "        right, stack = [n] * n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for num, l, r in zip(nums, left, right):\n",
    "            k = r - l - 1\n",
    "            if num > threshold // k:\n",
    "                return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 找到nums[i]作为最小值的数组\n",
    "        n = len(nums)\n",
    "        # 找到nums[i]右边第一个小于它的数的下标\n",
    "        # 从左往右单增\n",
    "        right = [n]*n\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]]>nums[i]:\n",
    "                right[st.pop()] = i\n",
    "            st.append(i)\n",
    "        \n",
    "        # 找到nums[i]左边第一个小于它的数的下标\n",
    "        # 从右往左单增\n",
    "        left = [-1]*n\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and nums[st[-1]]>nums[i]:\n",
    "                left[st.pop()] = i\n",
    "            st.append(i)\n",
    "        \n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        for i in range(n):\n",
    "            l = right[i]-left[i] - 1\n",
    "            if nums[i] > threshold/l:\n",
    "                return l\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法二: 单调栈\n",
    "# 枚举 nums[i] 为连续子数组最小者, 用两个数组left, right 记录 最近左边, 右边比 nums[i] 小的数下标\n",
    "# 此时 left[i]+1 是连续子数组的起点, right[i]-1 是连续子数组的终点\n",
    "# 连续子数组长为 (right[i]-1) - (left[i] + 1) + 1 = right[i] - left[i] - 1\n",
    "# \n",
    "# 因此需要用单调栈记录下标, 当 nums[i] 小于等于 栈顶下标的元素时, 弹出栈顶元素\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        left, st = [-1] * n, []\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and x <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:  left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        right, st = [n] * n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[i] <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:  right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        for x, r, l in zip(nums, right, left):\n",
    "            arr_len = r - l - 1\n",
    "            if x > threshold / arr_len:\n",
    "                return arr_len\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 方法一: 并查集\n",
    "        # fa = list(range(n + 1))\n",
    "        # sz = [1] * (n + 1)\n",
    "\n",
    "        # def find(x: int) -> int:    # 找到 x 的根节点(本题为最右端的数下标)\n",
    "        #     if fa[x] != x:\n",
    "        #         fa[x] = find(fa[x])\n",
    "            \n",
    "        #     return fa[x]\n",
    "        \n",
    "        # # 将数字从大到小排序\n",
    "        # for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "        #     # 在初始时, 下标 i 的根节点就是自己, 因此需要找下一个下标 i + 1 的根节点\n",
    "        #     j = find(i+1)\n",
    "        #     fa[i] = j # 更新 下标i 的根节点\n",
    "        #     sz[j] += sz[i]\n",
    "        #     arr_len = sz[j] - 1\n",
    "        #     # 因为从大到小遍历, 因此可以确保此时 num 是长为 arr_len 的连续子数组的最小值\n",
    "        #     if num > threshold / arr_len:\n",
    "        #         return arr_len\n",
    "        \n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "\n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]] >= nums[i]:\n",
    "                st.pop()\n",
    "            if st: l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[st[-1]] >= nums[i]:\n",
    "                st.pop()\n",
    "            if st: r[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            k = r[i] - l[i] - 1\n",
    "            if nums[i] > (threshold / k):\n",
    "                return k\n",
    "        return -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 方法二: 单调栈\n",
    "# 用两个数组left, right 找到 最近左边, 右边比 nums[i] 小的数下标, 这样可以保证 nums[i] 是这段子数组的最小数\n",
    "# 此时 left[i]+1 是连续子数组的起点, right[i]-1 是连续子数组的终点\n",
    "# 连续子数组长为 (right[i]-1) - (left[i] + 1) + 1 = right[i] - left[i] - 1\n",
    "# \n",
    "# 因此需要用单调栈记录下标, 当 nums[i] 小于等于 栈顶下标的元素时, 弹出栈顶元素\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        left, st = [-1] * n, []\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and x <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:  left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        right, st = [n] * n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while st and nums[i] <= nums[st[-1]]:\n",
    "                st.pop()\n",
    "            if st:  right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        for x, r, l in zip(nums, right, left):\n",
    "            arr_len = r - l - 1\n",
    "            if x > threshold / arr_len:\n",
    "                return arr_len\n",
    "        \n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 方法一: 并查集\n",
    "        # fa = list(range(n + 1))\n",
    "        # sz = [1] * (n + 1)\n",
    "\n",
    "        # def find(x: int) -> int:    # 找到 x 的根节点(本题为最右端的数下标)\n",
    "        #     if fa[x] != x:\n",
    "        #         fa[x] = find(fa[x])\n",
    "            \n",
    "        #     return fa[x]\n",
    "        \n",
    "        # # 将数字从大到小排序\n",
    "        # for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "        #     # 在初始时, 下标 i 的根节点就是自己, 因此需要找下一个下标 i + 1 的根节点\n",
    "        #     j = find(i+1)\n",
    "        #     fa[i] = j # 更新 下标i 的根节点\n",
    "        #     sz[j] += sz[i]\n",
    "        #     arr_len = sz[j] - 1\n",
    "        #     # 因为从大到小遍历, 因此可以确保此时 num 是长为 arr_len 的连续子数组的最小值\n",
    "        #     if num > threshold / arr_len:\n",
    "        #         return arr_len\n",
    "        \n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 用单调栈求下一个大（或小）的元素，看到这种想单调栈；本题关键在于找到以某个元素为中心的字串\n",
    "        n = len(nums)\n",
    "        # left[i] 为左侧小于nums[i]的最近元素的位置，如果不存在的话，则为-1\n",
    "        left, stack = [-1] * n, []\n",
    "        for i, v in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] >= v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        # right[i] 为右侧小于nums[i]的最近元素的位置，如果不存在，则为n\n",
    "        right, stack = [n] * n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        for num, l, r in zip(nums, left, right):\n",
    "            k = r - l - 1\n",
    "            if num > threshold // k:\n",
    "                return k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            leng = right[i] - left[i] - 1\n",
    "            if threshold / leng < nums[i]:\n",
    "                return leng\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n \n",
    "        stack = []\n",
    "        for i, j in enumerate(nums):\n",
    "            while stack and nums[stack[-1]] >= j:\n",
    "                right[stack.pop()] = i \n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            cur_len = right[i] - left[i] - 1\n",
    "            if nums[i] > threshold / cur_len:\n",
    "                return cur_len \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and nums[stk[-1]] >= x:\n",
    "                right[stk.pop()] = i\n",
    "            if stk: left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x * (right[i] - left[i] - 1) > threshold:\n",
    "                return right[i] - left[i] - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                right[stack.pop()] = i\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        for i in range(n):\n",
    "            leng = right[i] - left[i] - 1\n",
    "            if threshold / leng < nums[i]:\n",
    "                return leng\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = [-1]*n,[n]*n\n",
    "        st = []\n",
    "        for i in range(n):\n",
    "            while st and nums[st[-1]] > nums[i]:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "\n",
    "            st.append(i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            if threshold / nums[i] < r[i] - l[i] - 1:\n",
    "                return r[i] - l[i] - 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left,right = [-1]*n,[n]*n\n",
    "        st = []\n",
    "        for i,x in enumerate(nums):\n",
    "            while st and nums[st[-1]] > x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        for x,l,r in zip(nums,left,right):\n",
    "            if x*(r-l-1) > threshold: return r-l-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [-1] * n\n",
    "        r = [n] * n\n",
    "        stk = [-1]\n",
    "        for i in range(n):\n",
    "            while len(stk) > 1 and nums[stk[-1]] >= nums[i]:\n",
    "                # r[stk[-1]] = i\n",
    "                stk.pop()\n",
    "            l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        stk = [-1]\n",
    "        for i in range(n):\n",
    "            while len(stk) > 1 and nums[stk[-1]] > nums[i]:\n",
    "                r[stk[-1]] = i\n",
    "                stk.pop()\n",
    "            # l[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        # print(l)\n",
    "        # print(r)\n",
    "        \n",
    "        for i in range(n):\n",
    "            tmp = threshold // nums[i] + 1\n",
    "            if tmp <= r[i] - l[i] - 1:\n",
    "                return tmp\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 模板：经典单调栈前后边界下标计算\n",
    "        n = len(nums)\n",
    "        post = [n - 1] * n   # 这里可以是n/n-1/null，取决于用途\n",
    "        pre = [0] * n   # 这里可以是0/-1/null，取决于用途\n",
    "        stack = []\n",
    "        for i in range(n):  # 这里也可以是从n-1到0倒序计算，取决于用途\n",
    "            while stack and nums[stack[-1]] > nums[i]:  # 这里可以是\"<\" \">\" \"<=\" \">=\"，取决于需要判断的大小关系\n",
    "                post[stack.pop()] = i - 1  # 这里可以是i或者i-1，取决于是否包含i作为右端点\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):  # 这里也可以是从n-1到0倒序计算，取决于用途\n",
    "            while stack and nums[stack[-1]] > nums[i]:  # 这里可以是\"<\" \">\" \"<=\" \">=\"，取决于需要判断的大小关系\n",
    "                pre[stack.pop()] = i + 1  # 这里可以是i或者i-1，取决于是否包含i作为右端点\n",
    "            stack.append(i)\n",
    "            \n",
    "        for i in range(n):\n",
    "            left, right = pre[i], post[i]\n",
    "            if (right-left+1)*nums[i]>threshold:\n",
    "                return right-left+1\n",
    "       \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        indexes = [i for i in range(n)]\n",
    "        indexes.sort(key=lambda i: -nums[i])\n",
    "        count = [0] * n\n",
    "        for i in indexes:\n",
    "            left = i - count[i-1] if i > 0 else i\n",
    "            right = i + count[i+1] if i + 1 < n else i\n",
    "            k = right - left + 1\n",
    "            if nums[i] > threshold / k:\n",
    "                return k\n",
    "            count[left] = k\n",
    "            count[right] = k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 前后缀分解可以知道以以x为最小值的最长序列\n",
    "        n = len(nums)\n",
    "        left = [0] * n \n",
    "        right = [0] * n\n",
    "        \n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = i - stack[-1][1] - 1\n",
    "            else:\n",
    "                left[i] = i\n",
    "            stack.append([x, i])\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = nums[i]\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1][1] - i - 1\n",
    "            else:\n",
    "                right[i] = n-1-i\n",
    "            stack.append([x, i])\n",
    "        \n",
    "        m = defaultdict(int)\n",
    "        for x, l, r in zip(nums, left, right):\n",
    "            v = l + r + 1\n",
    "            if v * x > threshold:\n",
    "                return v\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "\n",
    "        stack = []\n",
    "        for i, val in enumerate(nums):\n",
    "            while stack and stack[-1][1] >= val:\n",
    "                stack.pop()\n",
    "            if stack: left[i] = stack[-1][0]\n",
    "            stack.append((i, val))\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            val = nums[i]\n",
    "            while stack and stack[-1][1] > val:\n",
    "                stack.pop()\n",
    "            if stack: right[i] = stack[-1][0]\n",
    "            stack.append((i, val))\n",
    "        \n",
    "        for i, val in enumerate(nums):\n",
    "            k = (right[i] - left[i] - 1)\n",
    "            if threshold // k < val:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        ranges = getRange(nums, isMax=False)\n",
    "        for i, (left, right) in enumerate(ranges):\n",
    "            if nums[i] > Fraction(threshold, (right - left + 1)):\n",
    "                return right - left + 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "def getRange(\n",
    "    nums: List[int],\n",
    "    *,\n",
    "    isMax=False,\n",
    "    isLeftStrict=False,\n",
    "    isRightStrict=False,\n",
    ") -> List[Tuple[int, int]]:\n",
    "    \"\"\"\n",
    "    求每个元素作为最值的影响范围(区间)\n",
    "    \"\"\"\n",
    "    def compareLeft(stackValue: int, curValue: int) -> bool:\n",
    "        if isLeftStrict and isMax:\n",
    "            return stackValue <= curValue\n",
    "        elif isLeftStrict and not isMax:\n",
    "            return stackValue >= curValue\n",
    "        elif not isLeftStrict and isMax:\n",
    "            return stackValue < curValue\n",
    "        else:\n",
    "            return stackValue > curValue\n",
    "\n",
    "    def compareRight(stackValue: int, curValue: int) -> bool:\n",
    "        if isRightStrict and isMax:\n",
    "            return stackValue <= curValue\n",
    "        elif isRightStrict and not isMax:\n",
    "            return stackValue >= curValue\n",
    "        elif not isRightStrict and isMax:\n",
    "            return stackValue < curValue\n",
    "        else:\n",
    "            return stackValue > curValue\n",
    "\n",
    "    n = len(nums)\n",
    "    leftMost = [0] * n\n",
    "    rightMost = [n - 1] * n\n",
    "\n",
    "    stack = []\n",
    "    for i in range(n):\n",
    "        while stack and compareRight(nums[stack[-1]], nums[i]):\n",
    "            rightMost[stack.pop()] = i - 1\n",
    "        stack.append(i)\n",
    "\n",
    "    stack = []\n",
    "    for i in range(n - 1, -1, -1):\n",
    "        while stack and compareLeft(nums[stack[-1]], nums[i]):\n",
    "            leftMost[stack.pop()] = i + 1\n",
    "        stack.append(i)\n",
    "\n",
    "    return list(zip(leftMost, rightMost))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n))\n",
    "        sz = [1] * n\n",
    "        def find(x: int) -> int:\n",
    "            cur = x\n",
    "            while x != fa[x]:\n",
    "                x = fa[x]\n",
    "            while fa[cur] != x:\n",
    "                fa[cur], cur = x, fa[cur]\n",
    "            return x\n",
    "        def union(x: int, y: int):\n",
    "            x, y = find(x), find(y)\n",
    "            if x == y: return\n",
    "            sz[y] += sz[x]\n",
    "            fa[x] = y\n",
    "\n",
    "        for x, i in sorted(zip(nums, range(n)), reverse = True):\n",
    "            if i > 0 and x <= nums[i - 1]:\n",
    "                union(i, i - 1)\n",
    "            if i < n - 1 and x <= nums[i + 1]:\n",
    "                union(i, i + 1)\n",
    "            i = find(i)\n",
    "            if x * sz[i] > threshold: return sz[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.F = [i for i in range(n)]\n",
    "        self.cnt = [0] * n\n",
    "    \n",
    "    def find(self,x):\n",
    "        while self.F[x]!=x:\n",
    "            x = self.F[x]\n",
    "        return x\n",
    "    \n",
    "    def union(self,a,b):\n",
    "        fa,fb = self.find(a),self.find(b)\n",
    "        if self.cnt[fa] <= self.cnt[fb]:\n",
    "            self.cnt[fa] += self.cnt[fb]\n",
    "            self.F[fb] = self.F[fa]\n",
    "        else:\n",
    "            self.cnt[fb] += self.cnt[fa]\n",
    "            self.F[fa] = self.F[fb]\n",
    "            \n",
    "class Solution: \n",
    "    def validSubarraySize(self, nums: List[int], ts: int) -> int:\n",
    "        n = len(nums)\n",
    "        uf = UnionFind(n)\n",
    "        q = []\n",
    "        for idx,i in enumerate(nums):\n",
    "            heappush(q,[-i,idx])\n",
    "        for l in range(1,n+1):\n",
    "            while -q[0][0] > ts/l:\n",
    "                _,idx = heappop(q)\n",
    "                uf.cnt[idx] = 1\n",
    "                if idx+1 < n and uf.cnt[idx+1]:uf.union(idx,idx+1)\n",
    "                if idx-1 >= 0 and uf.cnt[idx-1]:uf.union(idx,idx-1)\n",
    "                if uf.cnt[uf.find(idx)] >= l:return l\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegTreeMax:\n",
    "    def __init__(self, n):\n",
    "        self.nums = [0] * (4*n)\n",
    "\n",
    "    # 某个结点的标号node，区间左侧left，区间右侧right，添加的位置idx，添加的值val\n",
    "    def add(self, node, left, right, idx, val):\n",
    "        if left == right:\n",
    "            self.nums[node] = val\n",
    "            return\n",
    "        mid = (right + left) // 2\n",
    "        if idx <= mid:\n",
    "            self.add(2 * node + 1, left, mid, idx, val)\n",
    "        else:\n",
    "            self.add(2 * node + 2, mid + 1, right, idx, val)\n",
    "        self.nums[node] = max(self.nums[2*node+1], self.nums[2*node+2])\n",
    "\n",
    "    # 某个结点的标号node，区间左侧left，区间右侧right ; [interval_l, interval_r] 表示需要查询的区间和\n",
    "    def query(self, node, left, right, interval_l, interval_r):\n",
    "        # 其实要讨论三种情况：1、查询的区间都在mid的左侧 2、查询的区间都在mid的右侧  3、卡在中间\n",
    "        if left == interval_l and right == interval_r:\n",
    "            return self.nums[node]\n",
    "        mid = (right + left) // 2\n",
    "        if interval_r <= mid:\n",
    "            return self.query(2 * node + 1, left, mid, interval_l, interval_r)\n",
    "        elif interval_l > mid:\n",
    "            return self.query(2 * node + 2, mid + 1, right, interval_l, interval_r)\n",
    "        else:\n",
    "            return max(self.query(2 * node + 1, left, mid, interval_l, mid),\n",
    "                       self.query(2 * node + 2, mid + 1, right, mid + 1, interval_r))\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        # 前后缀分解可以知道以以x为最小值的最长序列\n",
    "        n = len(nums)\n",
    "        left = [0] * n \n",
    "        right = [0] * n\n",
    "        \n",
    "        stack = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = i - stack[-1][1] - 1\n",
    "            else:\n",
    "                left[i] = i\n",
    "            stack.append([x, i])\n",
    "\n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            x = nums[i]\n",
    "            while stack and stack[-1][0] >= x:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1][1] - i - 1\n",
    "            else:\n",
    "                right[i] = n-1-i\n",
    "            stack.append([x, i])\n",
    "        \n",
    "        m = defaultdict(int)\n",
    "        for x, l, r in zip(nums, left, right):\n",
    "            m[x] = max(m[x], 1 + l + r)\n",
    "        \n",
    "        # 下一步不是要写一个线段树吧\n",
    "        arr =sorted([[k, m[k]] for k in m])\n",
    "        keys = [k for k,v in arr]\n",
    "        values = [v for k, v in arr]\n",
    "        \n",
    "        n = len(keys)\n",
    "        tree = SegTreeMax(n)\n",
    "        for i in range(n):\n",
    "            tree.add(node=0, left=0, right=n-1, idx=i, val=values[i])\n",
    "        \n",
    "        ans = -1\n",
    "        for k in range(1, max(values)+1) :\n",
    "            v = ceil((threshold + 1) / k)\n",
    "            idx = bisect_left(keys, v)\n",
    "            if idx == n:\n",
    "                continue\n",
    "            if tree.query(node=0, left=0, right=n-1, interval_l=idx, interval_r=n-1) >= k:\n",
    "                ans = k\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "        \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n))\n",
    "        l = [1] * n\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        vis = [0] * n\n",
    "        for i in sorted(range(n), key=lambda i: -nums[i]):\n",
    "            if i > 0 and vis[i-1]:\n",
    "                p = find(i-1)\n",
    "                fa[i] = p\n",
    "                l[p] += 1\n",
    "            if i+1 < n and vis[i+1]:\n",
    "                p, q = find(i), find(i+1)\n",
    "                fa[q] = p\n",
    "                l[p] += l[q]\n",
    "            k = l[find(i)]\n",
    "            if nums[i] > threshold / k:\n",
    "                return k\n",
    "            vis[i] = 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        pa = list(range(n))\n",
    "        we = [1] * n\n",
    "        def find(x):\n",
    "            if pa[x] != x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(i,j):\n",
    "            x,y = map(find,[i,j])\n",
    "            if x == y: return\n",
    "            if we[x] < we[y]: x,y = y,x\n",
    "            pa[y] = x\n",
    "            we[x] += we[y]\n",
    "        for x,i in sorted(zip(nums,range(n)),reverse=True):\n",
    "            if i > 0 and nums[i-1] >= x: union(i,i-1)\n",
    "            if i < n-1 and nums[i+1] >= x: union(i,i+1)\n",
    "            if x * we[find(i)] > threshold: return we[find(i)]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j  # 合并 i 和 i+1\n",
    "            sz[j] += sz[i] + 1\n",
    "            if num > threshold // sz[j]: return sz[j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n+1))\n",
    "        sz = [1] * (n+1)\n",
    "\n",
    "        # 从x出发，找到根节点（返回x所在集合的根节点）\n",
    "        # 对于本题来说是链的最右端\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            # merge i and i+1\n",
    "            j = find(i+1)\n",
    "            fa[i] = j\n",
    "            sz[j] += sz[i]\n",
    "            arr_size = sz[j] - 1\n",
    "            if num > threshold / arr_size:\n",
    "                return arr_size\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n+1))\n",
    "        sz = [1] * (n+1)\n",
    "\n",
    "        # 从x出发，找到根节点（返回x所在集合的根节点）\n",
    "        # 对于本题来说是链的最右端\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            # merge i and i+1\n",
    "            j = find(i+1)\n",
    "            fa[i] = j\n",
    "            sz[j] += sz[i]\n",
    "            arr_size = sz[j] - 1\n",
    "            if num > threshold / arr_size:\n",
    "                return arr_size\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j  # 合并 i 和 i+1\n",
    "            sz[j] += sz[i] + 1\n",
    "            if num > threshold // sz[j]: return sz[j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j  # 合并 i 和 i+1\n",
    "            sz[j] += sz[i] + 1\n",
    "            if num > threshold // sz[j]: return sz[j]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [1] * (n + 1)\n",
    "\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for val, i in sorted(zip(nums,  range(n)), reverse = True):\n",
    "            print(i, val)\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j\n",
    "            sz[j] += sz[i]\n",
    "            arr_len = sz[j] - 1\n",
    "            if val > threshold // arr_len:\n",
    "                return arr_len\n",
    "        \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            fa[i] = find(i + 1)\n",
    "            sz[fa[i]] += sz[i] + 1\n",
    "            if num > threshold // sz[fa[i]]: return sz[fa[i]]\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [1] * (n + 1)\n",
    "\n",
    "        def find(x: int) -> int:    # 找到 x 的根节点(本题为最右端的数下标)\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            \n",
    "            return fa[x]\n",
    "        \n",
    "        # 将数字从大到小排序\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            # 在初始时, 下标 i 的根节点就是自己, 因此需要找下一个下标 i + 1 的根节点\n",
    "            j = find(i+1)\n",
    "            fa[i] = j # 更新 下标i 的根节点\n",
    "            sz[j] += sz[i]\n",
    "            arr_len = sz[j] - 1\n",
    "            # 因为从大到小遍历, 因此可以确保此时 num 是连续子数组的最小值\n",
    "            if num > threshold / arr_len:\n",
    "                return arr_len\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        # 初始化并查集和大小数组\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        \n",
    "        # 并查集的查找操作\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        # 按值从大到小遍历数组\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j  # 合并 i 和 i+1\n",
    "            sz[j] += sz[i] + 1\n",
    "            if num > threshold // sz[j]: \n",
    "                return sz[j]\n",
    "                \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "        fa = list(range(n + 1))\n",
    "        sz = [0] * (n + 1)\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\n",
    "            j = find(i + 1)\n",
    "            fa[i] = j  # 合并 i 和 i+1\n",
    "            sz[j] += sz[i] + 1\n",
    "            if num > threshold // sz[j]: return sz[j]\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # 并查集\r\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        fa = list(range(n + 1))\r\n",
    "        sz = [0] * (n + 1)\r\n",
    "        def find(x: int) -> int:\r\n",
    "            if fa[x] != x:\r\n",
    "                fa[x] = find(fa[x])\r\n",
    "            return fa[x]\r\n",
    "        for num, i in sorted(zip(nums, range(n)), reverse=True):\r\n",
    "            j = find(i + 1)\r\n",
    "            fa[i] = j  # 合并 i 和 i+1\r\n",
    "            sz[j] += sz[i] + 1\r\n",
    "            if num > threshold // sz[j]: return sz[j]\r\n",
    "        return -1\r\n",
    "    \r\n",
    "    # 单调栈\r\n",
    "    def validSubarraySize2(self, nums: List[int], threshold: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        left, st = [-1] * n, []  # left[i] 为左侧小于 nums[i] 的最近元素位置（不存在时为 -1）\r\n",
    "        for i, v in enumerate(nums):\r\n",
    "            while st and nums[st[-1]] >= v: st.pop()\r\n",
    "            if st: left[i] = st[-1]\r\n",
    "            st.append(i)\r\n",
    "\r\n",
    "        right, st = [n] * n, []  # right[i] 为右侧小于 nums[i] 的最近元素位置（不存在时为 n）\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            while st and nums[st[-1]] >= nums[i]: st.pop()\r\n",
    "            if st: right[i] = st[-1]\r\n",
    "            st.append(i)\r\n",
    "\r\n",
    "        for num, l, r in zip(nums, left, right):\r\n",
    "            k = r - l - 1\r\n",
    "            if num > threshold // k: return k\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 并查集的大小（不包含并查根）\n",
    "        siz = [0] * (n + 1)\n",
    "\n",
    "        # 向右合并，并查根在最右侧\n",
    "        # 末尾额外添加一个哨兵，作为所有节点的根\n",
    "        fa = list(range(n + 1))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        for num, i in sorted(zip(nums, range(n)), reverse = True):\n",
    "            # 合并i，i + 1\n",
    "            fa_idx = find(i + 1)\n",
    "            fa[i] = fa_idx\n",
    "            siz[fa_idx] += siz[i] + 1\n",
    "            # 子数组长度不包含并查根， 等于siz[i]\n",
    "            if num > (threshold // siz[fa_idx]):\n",
    "                return siz[fa_idx]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def validSubarraySize(self, nums: List[int], threshold: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        # 并查集的大小（不包含并查根）\n",
    "        siz = [1] * (n + 1)\n",
    "\n",
    "        # 向右合并，并查根在最右侧\n",
    "        # 末尾额外添加一个哨兵，作为所有节点的根\n",
    "        fa = list(range(n + 1))\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        for num, i in sorted(zip(nums, range(n)), reverse = True):\n",
    "            # 合并i，i + 1\n",
    "            fa_idx = find(i + 1)\n",
    "            fa[i] = fa_idx\n",
    "            siz[fa_idx] += siz[i]\n",
    "            # 子数组长度不包含并查根， 等于siz[i]\n",
    "            if num > (threshold // (siz[fa_idx] - 1)):\n",
    "                return siz[fa_idx] - 1\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
